package io.gimo.study.design_pattern.factory.abstract_factory.product;


import io.gimo.study.design_pattern.factory.abstract_factory.Searcher;

public class HashSearcher implements Searcher {

	@Override
	public int search(int[] target, int search_key) {
		// 除法取余法
		int hashLength = 13;
		// 哈希表长度
		int[] hash = new int[hashLength];
		// 创建hash
		for (int i = 0; i < target.length; i++) {
			insertHash(hash, hashLength, target[i]);
		}
		int result = search(hash, hashLength, search_key);
		return result;
	}

	private int search(int[] hash, int hashLength, int search_key) {
		// 哈希函数
		int hashAddress = search_key % hashLength;

		// 指定hashAdrress对应值存在但不是关键值，则用开放寻址法解决
		while (hash[hashAddress] != 0 && hash[hashAddress] != search_key) {
			hashAddress = (++hashAddress) % hashLength;
		}

		// 查找到了开放单元，表示查找失败
		if (hash[hashAddress] == 0)
			return -1;
		return hashAddress;
	}

	private void insertHash(int[] hash, int hashLength, int data) {
		// 哈希函数
		int hashAddress = data % hashLength;

		// 如果key存在，则说明已经被别人占用，此时必须解决冲突
		while (hash[hashAddress] != 0) {
			// 用开放寻址法找到
			hashAddress = (++hashAddress) % hashLength;
		}

		// 将data存入字典中
		hash[hashAddress] = data;

	}

}
